home *** CD-ROM | disk | FTP | other *** search
/ Komputer for Alle 2004 #2 / K-CD-2-2004.ISO / OpenOffice Sv / f_0397 / python-core-2.2.2 / lib / test / test_mutants.py < prev    next >
Encoding:
Python Source  |  2003-07-18  |  8.2 KB  |  286 lines
  1. from test_support import verbose, TESTFN
  2. import random
  3. import os
  4.  
  5. # From SF bug #422121:  Insecurities in dict comparison.
  6.  
  7. # Safety of code doing comparisons has been an historical Python weak spot.
  8. # The problem is that comparison of structures written in C *naturally*
  9. # wants to hold on to things like the size of the container, or "the
  10. # biggest" containee so far, across a traversal of the container; but
  11. # code to do containee comparisons can call back into Python and mutate
  12. # the container in arbitrary ways while the C loop is in midstream.  If the
  13. # C code isn't extremely paranoid about digging things out of memory on
  14. # each trip, and artificially boosting refcounts for the duration, anything
  15. # from infinite loops to OS crashes can result (yes, I use Windows <wink>).
  16. #
  17. # The other problem is that code designed to provoke a weakness is usually
  18. # white-box code, and so catches only the particular vulnerabilities the
  19. # author knew to protect against.  For example, Python's list.sort() code
  20. # went thru many iterations as one "new" vulnerability after another was
  21. # discovered.
  22. #
  23. # So the dict comparison test here uses a black-box approach instead,
  24. # generating dicts of various sizes at random, and performing random
  25. # mutations on them at random times.  This proved very effective,
  26. # triggering at least six distinct failure modes the first 20 times I
  27. # ran it.  Indeed, at the start, the driver never got beyond 6 iterations
  28. # before the test died.
  29.  
  30. # The dicts are global to make it easy to mutate tham from within functions.
  31. dict1 = {}
  32. dict2 = {}
  33.  
  34. # The current set of keys in dict1 and dict2.  These are materialized as
  35. # lists to make it easy to pick a dict key at random.
  36. dict1keys = []
  37. dict2keys = []
  38.  
  39. # Global flag telling maybe_mutate() wether to *consider* mutating.
  40. mutate = 0
  41.  
  42. # If global mutate is true, consider mutating a dict.  May or may not
  43. # mutate a dict even if mutate is true.  If it does decide to mutate a
  44. # dict, it picks one of {dict1, dict2} at random, and deletes a random
  45. # entry from it; or, more rarely, adds a random element.
  46.  
  47. def maybe_mutate():
  48.     global mutate
  49.     if not mutate:
  50.         return
  51.     if random.random() < 0.5:
  52.         return
  53.  
  54.     if random.random() < 0.5:
  55.         target, keys = dict1, dict1keys
  56.     else:
  57.         target, keys = dict2, dict2keys
  58.  
  59.     if random.random() < 0.2:
  60.         # Insert a new key.
  61.         mutate = 0   # disable mutation until key inserted
  62.         while 1:
  63.             newkey = Horrid(random.randrange(100))
  64.             if newkey not in target:
  65.                 break
  66.         target[newkey] = Horrid(random.randrange(100))
  67.         keys.append(newkey)
  68.         mutate = 1
  69.  
  70.     elif keys:
  71.         # Delete a key at random.
  72.         i = random.randrange(len(keys))
  73.         key = keys[i]
  74.         del target[key]
  75.         # CAUTION:  don't use keys.remove(key) here.  Or do <wink>.  The
  76.         # point is that .remove() would trigger more comparisons, and so
  77.         # also more calls to this routine.  We're mutating often enough
  78.         # without that.
  79.         del keys[i]
  80.  
  81. # A horrid class that triggers random mutations of dict1 and dict2 when
  82. # instances are compared.
  83.  
  84. class Horrid:
  85.     def __init__(self, i):
  86.         # Comparison outcomes are determined by the value of i.
  87.         self.i = i
  88.  
  89.         # An artificial hashcode is selected at random so that we don't
  90.         # have any systematic relationship between comparison outcomes
  91.         # (based on self.i and other.i) and relative position within the
  92.         # hash vector (based on hashcode).
  93.         self.hashcode = random.randrange(1000000000)
  94.  
  95.     def __hash__(self):
  96.         return self.hashcode
  97.  
  98.     def __cmp__(self, other):
  99.         maybe_mutate()   # The point of the test.
  100.         return cmp(self.i, other.i)
  101.  
  102.     def __repr__(self):
  103.         return "Horrid(%d)" % self.i
  104.  
  105. # Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs,
  106. # where i and j are selected at random from the candidates list.
  107. # Return d.keys() after filling.
  108.  
  109. def fill_dict(d, candidates, numentries):
  110.     d.clear()
  111.     for i in xrange(numentries):
  112.         d[Horrid(random.choice(candidates))] = \
  113.             Horrid(random.choice(candidates))
  114.     return d.keys()
  115.  
  116. # Test one pair of randomly generated dicts, each with n entries.
  117. # Note that dict comparison is trivial if they don't have the same number
  118. # of entires (then the "shorter" dict is instantly considered to be the
  119. # smaller one, without even looking at the entries).
  120.  
  121. def test_one(n):
  122.     global mutate, dict1, dict2, dict1keys, dict2keys
  123.  
  124.     # Fill the dicts without mutating them.
  125.     mutate = 0
  126.     dict1keys = fill_dict(dict1, range(n), n)
  127.     dict2keys = fill_dict(dict2, range(n), n)
  128.  
  129.     # Enable mutation, then compare the dicts so long as they have the
  130.     # same size.
  131.     mutate = 1
  132.     if verbose:
  133.         print "trying w/ lengths", len(dict1), len(dict2),
  134.     while dict1 and len(dict1) == len(dict2):
  135.         if verbose:
  136.             print ".",
  137.         c = cmp(dict1, dict2)
  138.     if verbose:
  139.         print
  140.  
  141. # Run test_one n times.  At the start (before the bugs were fixed), 20
  142. # consecutive runs of this test each blew up on or before the sixth time
  143. # test_one was run.  So n doesn't have to be large to get an interesting
  144. # test.
  145. # OTOH, calling with large n is also interesting, to ensure that the fixed
  146. # code doesn't hold on to refcounts *too* long (in which case memory would
  147. # leak).
  148.  
  149. def test(n):
  150.     for i in xrange(n):
  151.         test_one(random.randrange(1, 100))
  152.  
  153. # See last comment block for clues about good values for n.
  154. test(100)
  155.  
  156. ##########################################################################
  157. # Another segfault bug, distilled by Michael Hudson from a c.l.py post.
  158.  
  159. class Child:
  160.     def __init__(self, parent):
  161.         self.__dict__['parent'] = parent
  162.     def __getattr__(self, attr):
  163.         self.parent.a = 1
  164.         self.parent.b = 1
  165.         self.parent.c = 1
  166.         self.parent.d = 1
  167.         self.parent.e = 1
  168.         self.parent.f = 1
  169.         self.parent.g = 1
  170.         self.parent.h = 1
  171.         self.parent.i = 1
  172.         return getattr(self.parent, attr)
  173.  
  174. class Parent:
  175.     def __init__(self):
  176.         self.a = Child(self)
  177.  
  178. # Hard to say what this will print!  May vary from time to time.  But
  179. # we're specifically trying to test the tp_print slot here, and this is
  180. # the clearest way to do it.  We print the result to a temp file so that
  181. # the expected-output file doesn't need to change.
  182.  
  183. f = open(TESTFN, "w")
  184. print >> f, Parent().__dict__
  185. f.close()
  186. os.unlink(TESTFN)
  187.  
  188. ##########################################################################
  189. # And another core-dumper from Michael Hudson.
  190.  
  191. dict = {}
  192.  
  193. # Force dict to malloc its table.
  194. for i in range(1, 10):
  195.     dict[i] = i
  196.  
  197. f = open(TESTFN, "w")
  198.  
  199. class Machiavelli:
  200.     def __repr__(self):
  201.         dict.clear()
  202.  
  203.         # Michael sez:  "doesn't crash without this.  don't know why."
  204.         # Tim sez:  "luck of the draw; crashes with or without for me."
  205.         print >> f
  206.  
  207.         return `"machiavelli"`
  208.  
  209.     def __hash__(self):
  210.         return 0
  211.  
  212. dict[Machiavelli()] = Machiavelli()
  213.  
  214. print >> f, str(dict)
  215. f.close()
  216. os.unlink(TESTFN)
  217. del f, dict
  218.  
  219.  
  220. ##########################################################################
  221. # And another core-dumper from Michael Hudson.
  222.  
  223. dict = {}
  224.  
  225. # let's force dict to malloc its table
  226. for i in range(1, 10):
  227.     dict[i] = i
  228.  
  229. class Machiavelli2:
  230.     def __eq__(self, other):
  231.         dict.clear()
  232.         return 1
  233.  
  234.     def __hash__(self):
  235.         return 0
  236.  
  237. dict[Machiavelli2()] = Machiavelli2()
  238.  
  239. try:
  240.     dict[Machiavelli2()]
  241. except KeyError:
  242.     pass
  243.  
  244. del dict
  245.  
  246. ##########################################################################
  247. # And another core-dumper from Michael Hudson.
  248.  
  249. dict = {}
  250.  
  251. # let's force dict to malloc its table
  252. for i in range(1, 10):
  253.     dict[i] = i
  254.  
  255. class Machiavelli3:
  256.     def __init__(self, id):
  257.         self.id = id
  258.  
  259.     def __eq__(self, other):
  260.         if self.id == other.id:
  261.             dict.clear()
  262.             return 1
  263.         else:
  264.             return 0
  265.  
  266.     def __repr__(self):
  267.         return "%s(%s)"%(self.__class__.__name__, self.id)
  268.  
  269.     def __hash__(self):
  270.         return 0
  271.  
  272. dict[Machiavelli3(1)] = Machiavelli3(0)
  273. dict[Machiavelli3(2)] = Machiavelli3(0)
  274.  
  275. f = open(TESTFN, "w")
  276. try:
  277.     try:
  278.         print >> f, dict[Machiavelli3(2)]
  279.     except KeyError:
  280.         pass
  281. finally:
  282.     f.close()
  283.     os.unlink(TESTFN)
  284.  
  285. del dict
  286.